package leetcode;

// https://leetcode-cn.com/problems/bulb-switcher/

public class Test319灯泡开关 {

    /*
    分析：要想找出 n 轮后有多少个亮着的灯泡，那必须先分析开关按几下灯才是亮的
    灯一开始是关闭的，显然必须按奇数次灯才是亮的

    问题变成n轮之后，有多少个开关被按了奇数次
    假设有4个开关，4轮之后有1,4两个开关被按了奇数次
    假设有5个开关，5轮之后有1,4两个开关被按了奇数次
    假设有6个开关，6轮之后有1,4两个开关被按了奇数次
    假设有7个开关，7轮之后有1,4两个开关被按了奇数次
    假设有8个开关，8轮之后有1,4两个开关被按了奇数次
    假设有9个开关，9轮之后有1,4,9三个开关被按了奇数次
        1 2 3 4 5 6 7 8 9
      1 1 1 1 1 1 1 1 1 1
      2   1   1   1   1
      3     1     1     1
      4       1       1
      5         1
      6           1
      7             1
      8               1
      9                  1

      观察如上矩阵，我们发现:
        对于第4个灯，在1，2，4轮被按下，有2个灯是亮的，4=1*4=2*2
        对于第6个灯，在1，2，3，6轮被按下，有2个灯是亮的，6=1*6=2*3
        对于第9个等，在1，3，9轮被按下，有3个灯是亮的，9=1*9=3*3
        再简化一下：
            4 2
            6 2
            9 3
        平方的关系
     */

    public static int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }

    public static void main(String[] args) {
        System.out.println(bulbSwitch(6));
    }
}
